/**
 *  @file PrintAndFreeInOrder.c
 *  @desc TODO 描述该文件的功能
 *  @author WangBlue(wangjiping596@gmail.com)
 *  @date 2025-07-23 9:11
 *  @version 1.0
 */


#include <stdio.h>
#include <stdlib.h>

// ------------------------- 结构体定义 -------------------------

/**
 * @brief 双向链表结点结构体
 */
typedef struct node {
    int data;               ///< 数据域
    struct node *next;      ///< 指向下一个节点
    struct node *pre;       ///< 指向上一个节点
} node, *link;

// ------------------------- 基础操作函数 -------------------------

/**
 * @brief 创建一个带数据的新结点
 * @param value 要存储的值
 * @return 成功返回新结点指针，失败返回 NULL
 */
link createNode(int value) {
    link newNode = (link) malloc(sizeof(node));
    if (newNode == NULL) return NULL;

    newNode->next = NULL;
    newNode->pre  = NULL;
    newNode->data = value;
    return newNode;
}

/**
 * @brief 初始化一个带头结点的空链表
 * @param head 指向链表头指针的地址
 */
void initNode(link *head) {
    link newNode = (link) malloc(sizeof(node));
    if (newNode == NULL) return;

    newNode->next = NULL;
    newNode->pre  = NULL;
    newNode->data = 0;  // 头结点不存储有效数据
    *head = newNode;
}

// ------------------------- 插入操作 -------------------------

/**
 * @brief 头插法，将新节点插入链表开头（头结点之后）
 * @param head 链表头指针
 * @param value 插入的数据
 */
void istHead(link head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;

    newNode->next = head->next;
    newNode->pre  = head;

    if (head->next != NULL)
        head->next->pre = newNode;

    head->next = newNode;
}

/**
 * @brief 尾插法，将新节点插入链表末尾
 * @param head 链表头指针
 * @param value 插入的数据
 */
void istTail(link head, int value) {
    link cur = head;
    while (cur->next != NULL) {
        cur = cur->next;
    }

    link newNode = createNode(value);
    if (newNode == NULL) return;

    cur->next = newNode;
    newNode->pre = cur;
}

// ------------------------- 打印链表 -------------------------

/**
 * @brief 从头到尾正向打印链表内容（跳过头结点）
 * @param head 链表头指针
 */
void printList(link head) {
    if (head == NULL || head->next == NULL) return;

    link cur = head->next;
    while (cur != NULL) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

// ------------------------- 删除操作 -------------------------

/**
 * @brief 删除链表中指定逻辑位置的结点（从 1 开始计数）
 * @param head 链表头指针
 * @param pos 要删除的位置（从 1 开始）
 */
void delByPos(link head, int pos) {
    if (head == NULL || head->next == NULL) return;

    int idx = 1;
    link cur = head->next;

    while (cur != NULL && idx < pos) {
        cur = cur->next;
        idx++;
    }

    if (cur == NULL) return;

    if (cur->pre != NULL)
        cur->pre->next = cur->next;

    if (cur->next != NULL)
        cur->next->pre = cur->pre;

    free(cur);
}

/**
 * @brief 在第 pos 个位置之前插入数据
 * @param head 链表头指针
 * @param value 要插入的值
 * @param pos 插入的位置（从 1 开始）
 */
void insertByPos(link head, int value, int pos) {
    if (head == NULL || pos < 1) return;

    link cur = head;
    int idx = 0;
    while (cur != NULL && idx < pos - 1) {
        cur = cur->next;
        idx++;
    }

    if (cur == NULL) return;

    link newNode = createNode(value);
    if (newNode == NULL) return;

    newNode->next = cur->next;
    newNode->pre  = cur;

    if (cur->next != NULL)
        cur->next->pre = newNode;

    cur->next = newNode;
}


/**
 * @brief 按升序逐个打印链表中的值并释放节点
 * @param head 双向链表头指针，必须带头节点
 * @note 每次找到当前最小值的节点，打印后释放，直到链表为空
 */
void printAndFreeInOrder(link head) {
    // 若链表为空 或 链表中没有实际数据节点
    if (head == NULL || head->next == NULL) return;

    // 每次循环移除一个最小节点，直到链表为空（只剩头节点）
    while (head->next != NULL) {
        link cur = head->next;  // 当前节点指针，从第一个数据节点开始
        link minNode = cur;     // 假设当前是最小节点

        // 遍历链表查找最小值节点
        while (cur->next != NULL) {
            // 如果找到更小的节点，则更新 minNode
            if (minNode->data > cur->next->data) {
                minNode = cur->next;
                cur = cur->next;
            } else {
                cur = cur->next;
            }
        }

        // 打印当前最小节点的值
        printf("value is %d\n", minNode->data);

        // 将 minNode 从链表中移除
        if (minNode->pre != NULL) {
            minNode->pre->next = minNode->next;
        }
        if (minNode->next != NULL) {
            minNode->next->pre = minNode->pre;
        }

        // 释放节点内存
        free(minNode);
    }
}

/**
 * @brief 主函数，测试 printAndFreeInOrder 的功能
 */
int main() {
    link head = NULL;

    // 初始化链表头节点
    initNode(&head);

    // 插入若干节点（尾插）：1 -> 2 -> 5 -> 3
    istTail(head, 1);
    istTail(head, 3);
    istTail(head, 2);
    istTail(head, 5);

    // 打印当前链表内容（打印顺序应为插入顺序）
    printList(head);

    // 按升序打印并释放链表中所有节点
    // 预期输出顺序：1, 2, 3, 5
    printAndFreeInOrder(head);

    return 0;
}
